﻿using System;
using System.Collections.Generic;
using System.Linq;
using Algoritmia.DataStructures.Maps;
using Algoritmia.Schemes;
using Algoritmia.Utils;
using Sets = Algoritmia.DataStructures.Sets;
using Algoritmia.StateSpaces;

namespace Algoritmia.Problems.PerfectHash.Basic
{
    public class PerfectHashStateSpace : IReversibleForwardStateSpace<PerfectHashStateSpace.State,int>
    {
        
        #region Inner Classes
        public class State
        {
            protected readonly Func<IMap<char, int>> _createMap;
            public readonly List<char> Chars ;

            public int Index;
            public IMap<char, int> G { get; private set; }

            public State(IEnumerable<string> words,Func<IMap<char,int>> createMap = null)
            {
                _createMap = createMap ?? (() => AlgoritmiaFactory.Maps<char, int>.Default);
                Chars = (from w in words
                          select w[0]).Union(from w in words
                                             select w.Last()).ToList();
                G = _createMap();
                Index = 0;
            }
        }

        #endregion

        protected readonly List<string> _words;
        protected readonly int _maxValue;
        protected readonly Func<int,Sets.ISet<int>> _createSet;

        public PerfectHashStateSpace(IEnumerable<string> words,int maxValue, Func<int,Sets.ISet<int>> createSet = null )
        {
            _words = words.ToList();
            _maxValue = maxValue;
            _createSet = createSet ?? (c => new Sets.IntSet(capacity: c));
        }

        #region Implementation of IForwardStateSpace<State,int>

        public State Decide(State state, int decision)
        {
            state.G[state.Chars[state.Index]] = decision;
            state.Index++;
            return state;
        }

        public IEnumerable<int> Decisions(State state)
        {
            for(int i = 0; i < _maxValue; i++)
            {
                if (ValueIsPromising(state,i))
                    yield return i;
            }
        }

        public IEnumerable<State> InitialStates
        {
            get { yield return new State(_words); }
        }

        public bool IsFinal(State state)
        {
            return state.Index == state.Chars.Count;
        }

        #endregion

        #region Implementation of IReversibleForwardStateSpace<State,int>

        public State Undo(State state, int decision)
        {
            state.Index--;
            state.G.Remove(state.Chars[state.Index]);
            return state;
        }

        #endregion

        private bool ValueIsPromising(State s,int n)
        {
            var used = _createSet(_maxValue+1);
            foreach(var w in _words)
            {
                int? a = null, b = null;
                char first = w[0];
                char last = w.Last();
                if (first == s.Chars[s.Index]) a = n;
                else if (s.G.Contains(first)) a = s.G[first];

                if (last == s.Chars[s.Index]) b = n;
                else if (s.G.Contains(last)) b = s.G[last];

                if (a != null && b != null)
                {
                    int h = w.Length + a.Value + b.Value;
                    if (used.Contains(h))
                    {
                        return false;
                    }
                    used.Add(h);
                }

            }
            return true;
        }

        public IEnumerable<KeyValuePair<string,int>> Solution(State finalState)
        {
            foreach(var word in _words)
            {
                var h = word.Length + finalState.G[word[0]] + finalState.G[word.Last()];
                yield return new KeyValuePair<string, int>(word,h);
            }
        }
    }

    public class PerfectHashFinder
    {
        private readonly BacktrackingEnumerator<PerfectHashStateSpace.State, int, IEnumerable<KeyValuePair<string, int>>> _enumerator;

        public PerfectHashFinder()
        {
            _enumerator =
                new BacktrackingEnumerator<PerfectHashStateSpace.State, int, IEnumerable<KeyValuePair<string, int>>> 
                    ( (space,i,decisions,f) => ((PerfectHashStateSpace)space).Solution(f));
        }

        public IEnumerable<KeyValuePair<string,int>> Find(IEnumerable<string> words,int maxValue)
        {
            var space = new PerfectHashStateSpace(words, maxValue);
            return _enumerator.First(space);
        }

    }
}
